10. Regular Expression Matching

Question

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

1. '.' Matches any single character.
2. '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial)

Example 1

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Solution 1: Recursive

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        ### 0 Pattern
        if p == "":
            return s == ""
        ### 1 Pattern
        if len(p) == 1:
            return (len(s) == 1) and (s[0] == p[0] or p[0] == '.')
        ### 2 or more Pattern
        else:
            # Deal with '.x' or 'xx'
            if p[1] != '*':
                if s == "":
                    return False
                else:
                    return (s[0] == p[0] or p[0] == '.') and self.isMatch(s[1:], p[1:])
            # Deal with 'x*' '.*'
            else:
                while(len(s) and (s[0] == p[0] or p[0] == '.')):
                    # Deal with zero* (e.g, (abcd | .*abcd))
                    if self.isMatch(s, p[2:]):
                      return True
                    s = s[1:]
                # Deal with the rest after '*'
                return self.isMatch(s, p[2:])

Time Complexity: O(N^2???)
Space Complexity: O(1)

Solution 2: Enhanced of Sol1

Time Complexity: O()
Space Complexity: O()

Solution 3: Dynamic Program

Time Complexity: O()
Space Complexity: O()

Reference

https://www.cnblogs.com/grandyang/p/4461713.html

Follow-up: Wildcard Matching

TODO

Time Complexity: O()
Space Complexity: O()